#include <stdio.h>
#include <stdlib.h>

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;

//栈 首元节点data记录个数
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *initStack() 
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = 0;
    node->next = NULL;
    return node;
}

void push(Node *S, int data) 
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = S->next;
    S->next = node;
    S->data++;
}

int isEmpty(Node *S)
{
    if (S->next == NULL || S->data == 0) return 1;
    return 0;
}

int pop(Node *S)
{   if (!isEmpty(S)) {
        Node *del = S->next;
        S->next = del->next;
        int ret = del->data;
        S->data--;
        free(del);
        return ret;
    }
    return -1;
}

Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void createGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] != 0) {
                G->arcNum++;
            }
        }
    }
    //G->arcNum /= 2;
}

int * findInDegress(Graph *G) 
{
    int *inDegress = (int *)malloc(sizeof(int) * G->vexNum);
    for (int j = 0; j < G->vexNum; j++) { //从列开始循环
        inDegress[j] = 0;//初始化
        for (int i = 0; i < G->vexNum; i++) {
            if (G->arcs[i][j]) {//有入
                inDegress[j]++;
            }
        }
    }
    return inDegress;
}

/**
 * 初始化一个入度数组inDegess
 * 思路：可以使用尾递归的思路
 * 1. 寻找inDegress为零的点 输出 并删除从它出来的边
 * 2. 循环第一步 直到 没有入度为零的点
 * 作用：判断图中是否有环 如果有那么顶点输出不完全
*/
//使用stack避免多次循环 提高速度
void topologicalSort(Graph *G)
{
    int *inDegress = findInDegress(G);
    Node *stack = initStack();
    for (int i = 0; i< G->vexNum; i++) { //首先入度为零入栈
        if (inDegress[i] == 0) {
            push(stack, i);
        }
    }
    //结果数组
    int *top = (int *)malloc(sizeof(int) * G->vexNum);
    int index = 0;
    while (!isEmpty(stack)) {
        int vex = pop(stack);
        top[index++] = vex;
        for (int j = 0; j < G->vexNum; j++) { 
            if (G->arcs[vex][j]) {
                inDegress[j]--;
                if (inDegress[j] == 0) {
                    push(stack, j);
                }
            }
        }
    }
    if (index < G->vexNum) printf("有环!\n");
    //显示结果
    for (int i = 0; i < index; i++) {
        printf("%c ", G->vexs[top[i]]);
    }
    putchar('\n');
    for (int i = 0; i < G->vexNum; i++) {
        printf("%d ", inDegress[i]);
    }
}

void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] == 1 && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);
        }
    }
}

int main(void)
{
    Graph* G = initGraph(6);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[6][6] = {
            0,1,1,1,0,0,
            0,0,0,0,0,0,
            0,1,0,0,1,0,
            0,0,0,0,1,0,
            0,0,0,0,0,0,
            0,0,0,1,1,0
    };
    createGraph(G, "123456", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    topologicalSort(G);
    printf("\n%d\n", G->arcNum);
    return 0;
}